package nachos.vm;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;
import nachos.vm.*;

import java.util.Formatter;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;
import java.util.List;
import java.util.ArrayList;
import java.util.Random;

/**
 * An inverted page table, used to support mapping virtual pages to
 * physical memory.
 */
public class InvertedPageTable {

    /**
     * Used to implement the second chance clock algorithm as
     * described in the book.
     */
    private int hand = 0;

    /**
     * The actual page table. The ith entry in the table corresponds
     * to the ith page of physical memory.
     */
    public Entry[] table;

    /**
     * Maps a (pid, vpn) pair to its index in the table.
     */
    private final Map<List<Integer>, Integer> index =
	new HashMap<List<Integer>, Integer>();
    
    /**
     * We need to store all the information contained in the
     * TranslationEntry, plus the pid, since we're using a single
     * table for all processes.
     */
    public static class Entry {
	int pid;
	TranslationEntry te;
	void invalidate() {
	    te.valid = false;
	    pid = -1;
	}
    }

    /**
     * Make a new inverted page table with n pages.
     */
    public InvertedPageTable(int n) {
	table = new Entry[n];
	for (int i = 0; i < n; i++) {
	    table[i] = new Entry();
	    table[i].pid = -1;
	    table[i].te = new TranslationEntry(-1, i, false, false, false, false);
	}
    }

    /**
     * Write the given translation entry to the appropriate slot
     * (whatever its value of ppn is), and associate it with the
     * given process id.
     */
    public void write(int pid, TranslationEntry te) {
	if (te.ppn < 0) {
	    throw new RuntimeException("Can't write translation entry with negative ppn");
	}
	table[te.ppn].pid = pid;
	table[te.ppn].te = te;

	index.put(key(pid, te.vpn), te.ppn);
    }

    /**
     * Return the entry for the given process id and virtual page
     * number. Note that this returns the entry itself, not a copy.
     */
    public TranslationEntry getEntry(int pid, int vpn, boolean throwIfMissing) {
	Integer idx = index.get(key(pid, vpn));
	Entry e = idx == null ? null : table[idx];
	
	if (e != null &&
	    e.te.vpn == vpn &&
	    e.te.valid &&
	    e.pid == pid)
	    return e.te;
	
	if (throwIfMissing)
	    throw new RuntimeException("Don't have vm entry for pid " + 
				       pid + " vpn " + vpn + "; vm is " +
				       this);
	return null;
    }


    /**
     * Find a suitable page to evict from virtual memory, using the
     * second chance clock algorithm.
     */
    public int nextVictim() {

	// Move the hand until we find an unused page, setting used to
	// false as we move past a page.
	while (table[hand].te.used) {
	    table[hand].te.used = false;
	    hand = (hand + 1) % table.length;
	}

	// Advance the hand once more so we don't end up swapping out
	// the same page twice in a row.
	int res = hand;
	hand = (hand + 1) % table.length;
	// Clock: 215 faults 0.001538%
	return res;
	// Random: 275, 261, 247

	// return random.nextInt(table.length);
    }

    private static final Random random = new Random();

    public String toString() {
	Formatter f = new Formatter()
	    .format("%n")
	    .format("%6s %6s %6s %5s %5s %5s %5s%n",
		    "PID", "VPN", "PPN", "Valid", "R.O.", "Used", "Dirty");
	for (Entry e : table) {
	    f.format("%6d %6d %6d %5b %5b %5b %5b%n",
		     e.pid, 
		     e.te.vpn, e.te.ppn, e.te.valid, e.te.readOnly, e.te.used, e.te.dirty);
			      
	}
	return f.toString();
    }

    /**
     * Returns the physical page number of an invalid page, or -1 if
     * there are no invalid pages.
     */
    public int findFreePage() {
	int ppn;
	for (ppn = 0; ppn < table.length; ppn++)
	    if (!table[ppn].te.valid)
		return ppn;
	return -1;
    }

    private List<Integer> key(int pid, int vpn) {
	return Arrays.asList(pid, vpn);
    }


    public List<Integer> invalidateProcess(int pid) {
	List<Integer> freedPages = new ArrayList<Integer>();
	for (Entry e : table) {
	    if (e.pid == pid &&
		e.te.valid) {
		freedPages.add(e.te.ppn);
		e.invalidate();
	    }
	}
	return freedPages;
    }

    public void markUsed(int ppn) {
	table[ppn].te.used = true;
    }

    public void markDirty(int ppn) {
	table[ppn].te.dirty = true;
    }
}